#pragma once
#ifndef COLAPRIORIDADIMP_CPP
#define COLAPRIORIDADIMP_CPP

#include "ColaPrioridadImp.h"

template <class T>
ColaPrioridadImp<T>::ColaPrioridadImp(nat largo, Puntero<FuncionHash<T>> fHash, Puntero<Comparador<T>> fComp, Puntero<Comparador<T>> fCompHash)
{
	this->fComparador = fComp;
	heap = Array<T>(largo+1);
	tope = 1;
	tablaHash = new TablaHash<T,nat>(fCompHash, fHash, largo);
	maxTamanio = largo;
}

template <class T>
ColaPrioridadImp<T>::~ColaPrioridadImp()
{

}

template <class T>
bool ColaPrioridadImp<T>:: EsVacia() const
{
    return tope == 1;
}

template <class T>
bool ColaPrioridadImp<T>:: EsLlena() const
{
    return tope == maxTamanio;
}

template <class T>
T& ColaPrioridadImp<T>:: Minimo()
{
	return heap[1];
}

template <class T>
void ColaPrioridadImp<T>:: Insertar(const T& e)
{	
	heap[tope] = e;
	tablaHash->Insertar(e,tope);
	Flotar(tope);
	tope++;
}

template <class T>
void ColaPrioridadImp<T>:: Flotar(nat pos)
{
	if(pos > 1)
	{
		int aux;
		T elem = heap[pos];
		for(aux = pos;this->fComparador->EsMayor(elem,heap[aux/2]);aux/=2)
		{
			IntercambiarEnHash(aux,aux/2);
		}
		heap[aux] = elem;
		tablaHash->Insertar(heap[aux],aux);
	}
		
}

template <class T>
void ColaPrioridadImp<T>::IntercambiarEnHash(nat pos1,nat pos2)
{
	T temp = heap[pos1];
	heap[pos1] = heap[pos2];
	heap[pos2] = temp;
	tablaHash->ActualizarValor(heap[pos1],pos1);
	tablaHash->ActualizarValor(heap[pos2],pos2);
}

template <class T>
void ColaPrioridadImp<T>:: Vaciar()
{
   tope=1;
}

template <class T>
void ColaPrioridadImp<T>::BorrarMinimo()
{
	heap[1] = heap[tope-1];
	tope--;
	Hundir(1);
}

template <class T>
void ColaPrioridadImp<T>::Hundir(nat pos)
{
	nat aux = pos;
	T e = heap[pos];
	while(2*aux <= tope)
	{
		nat hijoIzq = 2*aux;
		if(hijoIzq + 1 < tope && this->fComparador->EsMayor(heap[hijoIzq + 1],heap[hijoIzq]))
		{
			hijoIzq++;
		}

		if(this->fComparador->EsMayor(heap[hijoIzq],e))
		{
			IntercambiarEnHash(aux,hijoIzq);
		}
		else
		{
			break;
		}
		aux = hijoIzq;
	}
	heap[aux] = e;
	tablaHash->Insertar(heap[aux],e);
}

template <class T>
void ColaPrioridadImp<T>::ActualizarPrioridad(T& elem)
{
	nat posicionHash = tablaHash->Recuperar(elem);
	tablaHash->ActualizarValor(elem,posicionHash);
	Hundir(posicionHash);
	Flotar(posicionHash);	
}

#endif